package heap;

import java.util.*;

public class leetcode373查找和最小的K对数字 {
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        PriorityQueue<List<Integer>> queue = new PriorityQueue<>((o1, o2) -> o2.get(0) + o2.get(1) - o1.get(0) - o1.get(1));
        // 剪枝
        int length1 = Math.min(nums1.length, k);
        int length2 = Math.min(nums2.length, k);
        for (int i = 0; i < length1; i++) {
            for (int j = 0; j < length2; j++) {
                if (queue.size() == k) {
                    if (nums1[i] + nums2[j] < queue.peek().get(0) + queue.peek().get(1)) {
                        queue.poll();
                        queue.offer(Arrays.asList(nums1[i], nums2[j]));
                    }
                } else {
                    queue.offer(Arrays.asList(nums1[i], nums2[j]));
                }
            }
        }
        List<List<Integer>> result = new ArrayList<>();
        while (!queue.isEmpty()) {
            result.add(queue.poll());
        }
        return result;
    }
}
